package doubleLink;

public class DoubleLinkList {
    private int size;
    private Node head;
    private Node tail;

//    头插
    public void addFirst(int val){
        Node node = new Node(null,val,head);
        if(head == null){
            tail = node;
        }else{
            head.prev = node;
        }
        head = node;
        size++;
    }



//    尾插
    public void addLast(int val){
        Node node = new Node(tail,val,null);
        if(tail == null){
            head = node;
        }else{
            tail.next = node;
        }
        tail = node;
        size++;
    }
//    在index位置插入
    public void addIndex(int index,int val){
        if(legalIndex(index)){
            if(index == 0)addFirst(val);
            else if(index == size)addLast(val);
            else{
                Node prev = findIndexnode(index - 1);
                Node newNode = new Node(prev,val,prev.next);
                prev.next.prev = newNode;
                prev.next = newNode;
                size++; 
            }
        }
    }

//    删除一个结点
    private void unLink(Node node){
        Node prev = node.prev;
        Node next = node.next;
        if(prev == null){
            head = next;
        }else{
            prev.next = next;
            node.prev = null;
        }
        if(next == null){
            tail = prev;
        }else{
            next.prev = prev;
            node.next = null;
        }
        size--;
    }
//    头删


    public void removeFirst(){
        removeIndex(0);
    }
//    尾删
    public void removeLast(){
        removeIndex(size - 1);
    }
//    删除index位置的结点
    public void removeIndex(int index){
        if(legalIndex(index)){
            Node node = findIndexnode(index);
            unLink(node);
        }else{
            System.err.println("remove index illegal!");
        }
    }

//    删除第一次出现值为val的结点
    public void removeValueOnce(int val){
        for(Node x = head;x != null;x = x.next){
            if(x.val == val){
                unLink(x);
                break;
            }
        }
    }
//    删除所有值为val的结点
    public void removeValueAll(int val){
        for(Node x = head;x != null;){
            if(x.val == val){
                Node next = x.next;
                unLink(x);
                x = next;
            }else{
                x = x.next;
            }
        }
    }
//    修改结点
    public int reviseIndex(int index,int newVal){
        if(legalIndex(index)){
            Node node = findIndexnode(index);
            int oldVal = node.val;
            node.val = newVal;
            return oldVal;
        }else{
            System.err.println("reviseIndex index illegal!");
            return -1;
        }
    }
//    查找index位置的结点值
    public int findIndex(int index){
        if(legalIndex(index)){
            return findIndexnode(index).val;
        }else{
            System.err.println("findIndex index illegal!");
            return -1;
        }
    }

//    检查index合法性方法
    private boolean legalIndex(int index){
        if(index < 0 || index > size){
            return false;
        }
        return true;
    }
//    找到index位置结点
    private Node findIndexnode(int index){
        Node ret = null;
        if(index < size >> 1){
            ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        }else{
            ret = tail;
            for (int i = size - 1; i > index ; i--) {
                ret = ret.prev;
            }
        }
        return ret;
    }
//    打印链表
    public String toString() {
        String ret = "";
        Node node = head;
        while (node != null) {
            ret += node.val + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}
class Node {
    Node prev;
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }

    public Node(Node prev, int val, Node next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}